#ifndef LIST_H
#define LIST_H

#include<iostream>
using std::cout;

//一个类型去封装节点的指针构成一个自定义类型
//然后重载*、++等运算符，就可以达到普通指针执行下一个元素的行为

//链表节点
template<class T>
struct __ListNode{
	__ListNode(const T& x = T())
		:next(nullptr)
		,prev(nullptr)
		,data(x)
	{}

	__ListNode<T>* next;
	__ListNode<T>* prev;
	T data;
};

//链表迭代器
//T T& T*--->通过三个模版参数来决定返回的是T还是const T
template<class T,class Ref,class Ptr>
struct __list_iterator{

	typedef __ListNode<T> Node;
	typedef __list_iterator<T,Ref,Ptr> Self;
	Node* _node;

	__list_iterator(Node* node)
		:_node(node)
	{}

	//*it Ref代表的是T&或const T&
	Ref operator*(){
		return _node->data;
	}

	//it->  Ptr代表的是T*或const T*
	Ptr operator->(){
		return &_node->data;
	}

	//++it
	Self& operator++(){
		_node = _node->next;
		return *this;
	}

	//it++
	Self operator++(int){
		Self tmp(*this);
		++(*this);
		return tmp;
	}

	//--it
	Self& operator--(){
		_node = _node->prev;
		return *this;
	}

	//it--
	Self operator--(int){
		Self tmp(*this);
		--(*this);
		return tmp;
	}

	//it != end()
	bool operator!=(const Self& it){
		return _node != it._node;
	}

	bool operator==(const Self& it){
		return _node == it._node;
	}

};

template<class T>
class list{
	typedef __ListNode<T> Node;
public:
	typedef __list_iterator<T,T&,T*> iterator;
	typedef __list_iterator<T,const T&,const T*> const_iterator;

	list(){
		//空参构造一个带头双向循环链表，开始指向自己
		//头节点没有数据
		_head = new Node;
		_head->next = _head;
		_head->prev = _head;
	}

	list(const list& lt){
		//头节点没有数据
		_head = new Node;
		_head->next = _head;
		_head->prev = _head;

		//用迭代器一个一个尾插
		// const_iterator it = lt.begin();
		// while (it != lt.end())
		// {
		// 	push_back(*it);
		// 	++it;
		// }

		//也可以用for循环
		for(auto e: lt){
			push_back(e);
		}
		
	}
	list& operator=(const list& lt){
		if (this != &lt)
		{
			clear();
			for (auto e :lt)
			{
				push_back(e);
			}
			
		}
		
	}
	//begin是头节点的下一个位置
	iterator begin(){
		return iterator(_head->next);
	}
	//end是头节点 
	iterator end(){
		return iterator(_head);
	}

	//begin是头节点的下一个位置
	const_iterator begin() const{
		return const_iterator(_head->next);
	}
	//end是头节点 
	const_iterator end() const{
		return const_iterator(_head);
	}

	void push_back(const T& x){
		//保存目前最后的节点
		Node* tail = _head->prev;
		//新建节点
		Node* newnode = new Node(x);
		//插入:有没有数据插入的逻辑都是一样的
		tail->next = newnode;
		newnode->prev = tail;
		_head->prev = newnode;
		newnode->next = _head;

		//insert(end(),x);
	}
	void push_front(const T& x){
		insert(begin(),x);
	}
	
	void pop_back(){
		erase(--end());
	}
	void pop_front(){
		erase(begin());
	}

	//在pos的前一个位置插入
	void insert(iterator pos, const T& x){
		Node* cur = pos._node;//当前节点
		Node* prev = cur->prev;//插入的前一个节点
		Node* newnode = new Node(x);//新申请一个节点

		prev->next = newnode;
		newnode->prev = prev;
		newnode->next = cur;
		cur->prev = newnode;

	}
	void erase(iterator pos){
		if(pos == end()){
			cout << "不能删除头节点\n";
		}
		Node* cur = pos._node;//当前节点
		Node* prev = cur->prev;//删除节点的前一个节点
		Node* next = cur->next;//删除节点的后一个节点
		delete cur;

		prev->next = next;
		next->prev = prev;
	}

	//清掉除头节点之外的所有节点
	void clear(){
		iterator it = begin();
		while (it != end())
		{
			erase(it++);
		}
		
	}

	~list(){
		clear();
		delete _head;
		_head = nullptr;
	}
private:
	Node* _head;
};

#endif